#pragma once
#include<vector>
#include<iostream>
#include<iterator>
using namespace std;


class Hash
{
private:
	int initMaxSize = 16;
	int initValue = -1;
	int maxSize = initMaxSize;

	template<class T>
	void needMoreLocation(vector<T> &hashTable) {
		hashTable.insert(hashTable.end(), maxSize, initValue);
		maxSize *= 2;
		cout << "hashTable capacity * 2 completed ! " << endl;
	}

	template<class T>
	int findFinalLocation(vector<T> &hashTable,T num) {
		if (hashTable[hashTable.size() - 1] != -1)
			needMoreLocation(hashTable);
		int location = num % maxSize;
		while (hashTable[location] != -1) {
			location++;
		}
		return location;
	}

	template<class T>
	int findDeleteFinalLocation(vector<T> &hashTable, T num) {
		int location = num % maxSize;
		while (hashTable[location] != num) {
			location++;
		}
		return location;
	}

	template<class T>
	int findSearchFinalLocation(vector<T> &hashTable, T num) {
		int location = num % maxSize;
		for (int i = location; i < maxSize ; i++) {
			if (hashTable[i] == num) {
				return location;
			}
			if (i == maxSize - 1) {
				return -1;
			}
		}
	}


public:

	Hash();
	~Hash();
	
	template<class T>
	void HashInit(vector<T> &hashTable) {
		hashTable.insert(hashTable.begin(), initMaxSize,initValue);
		cout << "HashTable init complete." << endl;
		cout << "Now hashTable.size() = " << hashTable.size() << endl;
	}

	template<class T>
	void HashClearAll(vector<T> &hashTable) {
		hashTable.clear();
	}

	template<class T>
	void HashInsert(vector<T> &hashTable, T a) {
		int finalLocation = findFinalLocation(hashTable, a);
		hashTable[finalLocation] = a;
		cout << "Location " << finalLocation << " insert value " << a << " finished ! " << endl;
	}

	template<class T>
	void HashDelete(vector<T> &hashTable,T a) {
		int location = findDeleteFinalLocation(hashTable, a);
		hashTable[location] = -1;
		cout << "Location " << location << " delete finished ! " << endl;
	}

	template<class T>
	void HashSearch(vector<T> hashTable, T a) {
		int location = findSearchFinalLocation(hashTable, a);
		if (location != -1) {
			cout << "Find " << a << " is in " << location << endl;
		}
		else {
			cout << a << " not found ! " << endl;
		}
			
	}

	template<class T>
	void PrintAllElems(vector<T> Table) {
		int i;
		cout << "************************hashTable****************************" << endl;
		for (i = 0; i < Table.size(); i++) {
			cout << "*                 Location " << i << " save : " << Table[i] << "                       *"<<endl;
		}
		cout << "************************hashTable****************************" << endl;
	}
};

